﻿// 166. 数独 jinjiezhinna.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <set>
#include <bitset>
#include <assert.h>


using namespace std;
/*
https://www.acwing.com/problem/content/168/

数独 是一种传统益智游戏，你需要把一个 9×9 的数独补充完整，使得数独中每行、每列、每个 3×3 的九宫格内数字 1∼9 均恰好出现一次。

请编写一个程序填写数独。

输入格式
输入包含多组测试用例。

每个测试用例占一行，包含 81 个字符，代表数独的 81 个格内数据（顺序总体由上到下，同行由左到右）。

每个字符都是一个数字（1−9）或一个 .（表示尚未填充）。

您可以假设输入中的每个谜题都只有一个解决方案。

文件结尾处为包含单词 end 的单行，表示输入结束。

输出格式
每个测试用例，输出一行数据，代表填充完全后的数独。

输入样例：
4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......
......52..8.4......3...9...5.1...6..2..7........3.....6...1..........7.4.......3.
end
输出样例：
417369825632158947958724316825437169791586432346912758289643571573291684164875293
416837529982465371735129468571298643293746185864351297647913852359682714128574936
*/

const int N = 9;

int ones[1 << N],mmap[1<<N];
int row[N], col[N], cell[3][3];
char str[100];

inline int lowbit(int x) {
	return x & -x;
}

void init() {
	for (int i = 0; i < N; i++) {row[i] = col[i] = (1 << N) - 1;}

	for (int i = 0; i < 3; i++) {
		for (int j = 0; j < 3; j++) {
			cell[i][j] = (1<<N)-1;
		}
	}
}
inline int get(int x,int y) {
	return row[x] & col[y] & cell[x / 3][y / 3];
}

 
bool dfs(int cnt) {
	if (!cnt) return true;

	int minv = 10;
	int x, y;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (str[i * 9 + j] == '.') {
				int t = ones[get(i, j)];
				if (t < minv) {
					minv = t;
					x = i, y = j;
				}
			}
		}
	}

	for (int i = get(x, y); i; i -= lowbit(i)) {
		int t = mmap[lowbit(i)];
		row[x] -= 1 << t;
		col[y] -= 1 << t;
		cell[x / 3][y / 3] -= 1 << t;
		str[x * 9 + y] = '1' + t;
		if (dfs(cnt - 1)) return true;
		str[x * 9 + y] = '.';
		row[x] += 1 << t;
		col[y] += 1 << t;
		cell[x / 3][y / 3]+= 1 << t;
	}

	return false;
}


 
int main()
{
	for (int i = 0; i < N; i++) mmap[1 << i] = i;
	for (int i = 0; i < 1 << N; i++) {
		int s = 0;
		for (int j = i; j; j -= lowbit(j)) { s++; }
		ones[i] = s;
	}

	while (cin >> str, str[0] != 'e') {
		init();
		int cnt = 0;
		for (int i = 0, k = 0; i < N; i++) {
			for (int j = 0; j < N; j++, k++) {
				if (str[k] != '.') {
					int t = str[k] - '1';
					row[i] -= 1 << t;
					col[j] -= 1 << t;
					cell[i / 3][j / 3] -= 1 << t;
				}
				else {	cnt++;}
			}
		}

		dfs(cnt);
		cout << str << endl;
	}

	return 0;
}

